package 面试题.字节本地生活一面;

/**
 * @author: yan
 * @description: LeerCode 410 分割数组的最大值
 * @create: 2023-02-24 16:25
 **/

/**
 * 描述：
 * 输入：一个数组[1,2,3,4,5]，一个数n
 * 将数组分割为n份，求n份中的最大和
 *
 * 如 n = 3, 可以分为[1,2,3],[4],[5]
 * 返回最大和6
 *
 */

/**
 * 思路：二分 + 贪心
 *
 * 假设桶的容量为x，则x的最小值为数组中的最大值，最大值为数组的和
 * 对x进行二分，找到合适的容量
 *
 * 二分过程中需要判断容量为x时，需要的数量，这时与输入的数量对比，需要小于等于这个数量
 *
 * 时间复杂度
 * O(nums.length+log(r-l))
 *
 */
public class ByteDanceSolution1 {

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3,4,5,6};
        System.out.println(splitArray(nums, 2));
    }

    public static int splitArray(int[] nums, int k) {
        int l = 0, r = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > l)
                l = nums[i];
            r += nums[i];
        }
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (getBinNum(nums, mid) > k) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    /**
     * deep表示桶的容量
     *
     * @param arr
     * @param deep
     * @return 需要的桶数量
     */
    public static int getBinNum(int[] arr, int deep) {
        int binNum = 0;
        int tmpDeep = deep;
        for (int i = 0; i < arr.length; i++) {
            if (tmpDeep < arr[i]) {
                tmpDeep = deep - arr[i];
                binNum++;
            } else {
                tmpDeep -= arr[i];
            }
        }
        return binNum + 1;
    }

}
